package org.example;

// 双指针技巧秒杀七道数组题目
// 在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针
// 所谓左右指针，就是两个指针相向而行或者相背而行；
// 所谓快慢指针，就是两个指针同向而行，一快一慢。
// 对于单链表来说，大部分技巧都属于快慢指针，
// 单链表的六大解题套路 都涵盖了，比如链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。
public class DoublePointerToArrays {
    // 一：快慢指针技巧
    // 原地修改
    // 数组问题中比较常见的快慢指针技巧，是让你原地修改数组
    // 26. 删除有序数组中的重复项
    static class RemoveDuplicates {
        // 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
        // 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
        // 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
        // 返回 k

        // 如果不是原地修改的话，我们直接 new 一个 int[] 数组，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。
        //但是现在题目让你原地删除，不允许 new 新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。
        //由于数组已经排序，所以重复的元素一定连在一起，找出它们并不难。但如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到
        //O(N^2)

        // 高效解决这道题就是用到快慢指针技巧
        // 我们让慢指针slow走到后面，快指针fast走在前面探路，找到一个不重复的元素就赋值给slow并让slow前进一步。
        // 这样，就保证了nums[0..slow]都是无重复的元素，当fast指针遍历完整个数组nums后，nums[0..slow]就是整个数组去重之后的结果。
        public int removeDuplicates(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            int slow = 0;
            int fast = 0;
            while (fast < nums.length) {
                if (nums[fast] != nums[slow]) {
                    slow++;
                    // 维护nums[0..slow]无重复
                    nums[slow] = nums[fast];
                }
                fast++;
            }
            return slow + 1;
        }

        // 83. 删除排序链表中的重复元素(这里的是有序的单链表)
        // 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null) {
                if (fast.val != slow.val) {
                    // nums[slow] = nums[fast];
                    slow.next = fast;
                    // slow++;
                    slow = slow.next;
                }
                fast = fast.next;
            }
            // 断开与后面重复元素的连接
            slow.next = null;
            return head;
        }

        // 根据数组构建单链表
        public static ListNode arrayToListNode(int[] arr) {
            if (arr == null || arr.length == 0) {
                return null;
            }
            ListNode dummy = new ListNode(0);
            ListNode current = dummy;
            for (int num : arr) {
                current.next = new ListNode(num);
                current = current.next;
            }
            return dummy.next;
        }

        public static void main(String[] args) {
            int[] arr = {1, 1, 2, 3, 3};
            ListNode list = arrayToListNode(arr);
            new RemoveDuplicates().deleteDuplicates(list);
        }
    }

    // 除了让你在有序的数组/链表中去重，题目还可能让你对数组中的某些元素进行[原地删除]
    // 27. 移除元素
    // 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
    // 题目要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：
    // 如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。
    static class RemoveElement {
        public int removeElement(int[] nums, int val) {
            int fast = 0;
            int slow = 0;
            while (fast < nums.length) {
                if (nums[fast] != val) {
                    nums[slow] = nums[fast];
                    slow++;
                }
                fast++;
            }
            return slow;
        }
    }

    static class MoveZeroes {
        public void moveZeroes(int[] nums) {
            int fast = 0;
            int slow = 0;
            while (fast < nums.length) {
                if (nums[fast] != 0) {
                    nums[slow] = nums[fast];
                    slow++;
                }
                fast++;
            }
            for (int i = slow; i < nums.length; i++) {
                nums[i] = 0;
            }
            // 上述的for循环还可以这样写
//            for(; slow < nums.length; slow++){
//                nums[slow] = 0;
//            }
        }

        public static void main(String[] args) {
            int[] nums = {0, 1, 0, 3, 12};
            new MoveZeroes().moveZeroes(nums);
        }
    }
    // 滑动窗口
    // left指针在后，right指针在前，两个指针中间的部分就是[窗口]，算法通过扩大和缩小[窗口]来解决某些问题。
    // 滑动窗口查看 -> 滑动窗口算法核心框架详解


    // 二：左右指针的常用算法
    // 二分查找
    static class BinarySearch {
        public int binarySearch(int[] nums, int target) {
            // 一左一右两个指针相向而行
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = (right - left) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                }
            }
            return -1;
        }
    }
    // n数之和
    // 167. 两数之和 II - 输入有序数组
    /*
        给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
        如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
        以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
        你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
        你所设计的解决方案必须只使用常量级的额外空间。
        输入：numbers = [2,7,11,15], target = 9
        输出：[1,2]
        解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
    */

    // 只要数组有序，就应该想到双指针技巧。
    static class TwoSum {
        public int[] twoSum(int[] numbers, int target) {
            // 一左一右两个指针相向而行
            int left = 0;
            int right = numbers.length - 1;
            while (left < right) {
                int sum = numbers[left] + numbers[right];
                if (sum == target) {
                    // 题目要求的索引是从1开始的
                    return new int[]{left + 1, right + 1};
                } else if (sum < target) {
                    // 让sum大一点
                    left++;
                } else if (sum > target) {
                    right--;
                }
            }
            return new int[]{-1, -1};
        }
    }

    // 反转数组
    // 344. 反转字符串
    // 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
    // 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
    // 示例 1：
    // 输入：s = ["h","e","l","l","o"]
    // 输出：["o","l","l","e","h"]
    static class ReverseString {
        public void reverseString(char[] s) {
            // 一左一右两个指针相向而行
            int left = 0;
            int right = s.length - 1;
            while (left < right) {
                // 交换s[left]和s[right]
                char temp = s[left];
                s[left] = s[right];
                s[right] = temp;
                left++;
                right--;
            }
        }
    }

    // 回文串判断
    // 5. 最长回文子串
    // 给你一个字符串 s，找到 s 中最长的 回文 子串。
    // 示例 1：
    // 输入：s = "babad"
    // 输出："bab"
    // 解释："aba" 同样是符合题意的答案。

    // 回文子串：回文子串是指在一个字符串中，存在连续的子序列，该子序列从左到右和从右到左读起来是一样的。
    // 例如，在字符串 "abcba" 中，"abcba" 本身就是一个回文子串，同时 "bcb"、"c" 等也都是回文子串。
    // 找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，
    // 解决该问题的核心是从中心向两端扩散的双指针技巧。
    static class LongestPalindrome {
        public String longestPalindrome(String s) {
            String res = "";
            for (int i = 0; i < s.length(); i++) {
                // 以s[i]为中心的最长回文子串
                String s1 = palindrome(s, i, i);
                // 以s[i]和s[i+1]为中心的最长回文子串
                String s2 = palindrome(s, i, i + 1);
                // res = longest(res, s1, s2)
                res = res.length() > s1.length() ? res : s1;
                res = res.length() > s2.length() ? res : s2;
            }
            return res;
        }

        // 在s中寻找以s[left]和s[right]为中心的最长回文串
        private String palindrome(String s, int left, int right) {
            // 防止索引越界
            while (left >= 0 && right < s.length()
                    && s.charAt(left) == s.charAt(right)) {
                // 双指针，向两边展开
                left--;
                right++;
            }
            // 此时[left+1, right-1]就是最长回文串
            return s.substring(left + 1, right);
        }
        // 这样，如果输入相同的left和right，就相当于寻找长度为奇数的回文串，
        // 如果输入相邻的left和right，则相当于寻找长度为偶数的回文串。

    }
}
